package algorithm;

public class leetcode_0221 {
    public int maximalSquare(char[][] matrix) {
        int m=matrix.length;
        int n=matrix[0].length;
        int max=0;
        int [][] dp=new int[m][n];
        for(int i=0;i<m;++i){
            dp[i][0]=matrix[i][0]-'0';
            max=(max>matrix[i][0]-'0')?max:matrix[i][0]-'0';
        }
        for(int j=0;j<n;++j){
            dp[0][j]=matrix[0][j]-'0';
            max=(max>matrix[0][j]-'0')?max:matrix[0][j]-'0';
        }
        for(int i=1;i<m;++i){
            for(int j=1;j<n;++j){
                if(matrix[i][j]-'0'==0){
                    dp[i][j]=0;
                }
                else if(dp[i-1][j-1]*dp[i-1][j]*dp[i][j-1]==0){
                    dp[i][j]=matrix[i][j]-'0';
                    max=(max>dp[i][j])?max:dp[i][j];
                }
                else{
                    dp[i][j]=min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1;
                    max=(max>dp[i][j])?max:dp[i][j];
                }
            }
        }
        return max*max;
    }
    public int min(int a,int b,int c){
        if(a<b){
            return (a<c)?a:c;
        }
        else{
            return (b<c)?b:c;
        }
    }
}
